package com.xiaoyu.binaryTree;

import java.util.*;

/**
 * @program: DS_and_A
 * @description: TODO
 * @author: YuWenYi
 * @create: 2021-05-20 10:40
 **/
public class PostorderTraversal_145 {
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        postOrder(root, list);
        return list;
    }
    //递归写法,简单易懂
    public void postOrder(TreeNode root,List<Integer> list){
        if (root == null){
            return;
        }
        postOrder(root.left, list);
        postOrder(root.right, list);
        list.add(root.val);
    }

    //非递归写法:循环+显式栈
    /*
        接下来我们思考一下前序遍历和后序遍历之间的关系：
        前序遍历顺序为：根 -> 左 -> 右
        后序遍历顺序为：左 -> 右 -> 根
        如果1： 我们将前序遍历中节点插入结果链表尾部的逻辑，修改为将节点插入结果链表的头部
        那么结果链表就变为了：右 -> 左 -> 根
        如果2： 我们将遍历的顺序由从左到右修改为从右到左，配合如果1
        那么结果链表就变为了：左 -> 右 -> 根
        这刚好是后序遍历的顺序
        */
    public List<Integer> postorderTraversal1(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> list = new LinkedList<>();
        while (root!=null || !stack.isEmpty()){
           if (root != null){
               stack.push(root);
               //每次前序遍历时，都将节点写入结果链表头，而不是尾
               list.addFirst(root.val);
               //每次先遍历右节点，再遍历左节点
               root = root.right;
           }else {
               root = stack.pop();
               //每次先遍历右节点，再遍历左节点
               root = root.left;
           }
        }
        return list;
    }


    //递归写法二:前序遍历的改编!,将头左右改成头右左然后再翻转成左右头
    public List<Integer> postorderTraversal2(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> list = new LinkedList<>();
        //边往下挖边添加(倒着加构成后序遍历)
        while (root!=null || !stack.isEmpty()){
            if (root != null){
                //每次前序遍历时，都将节点写入结果链表头，而不是尾,这样就能直接将结果进行倒序存储
                list.addFirst(root.val);
                if (root.left != null){
                    stack.push(root.left);
                }
                //优先访问右结点
                root = root.right;
            }else {
                root = stack.pop();
            }
        }
        return list;
    }



    public static void main(String[] args) {
        PostorderTraversal_145 pt = new PostorderTraversal_145();

        TreeNode right = new TreeNode(3,new TreeNode(6),new TreeNode(7));
        TreeNode left = new TreeNode(2,new TreeNode(4),new TreeNode(5));
        TreeNode root = new TreeNode(1,left,right);

        System.out.println(pt.postorderTraversal2(root));
    }
}
